#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
int count = 0; 
bool IsSafe(int now[]) {
	if ((now[1] == now[2]) && (now[0] != now[1]))
		return false;
	if ((now[2] == now[3]) && (now[0] != now[2]))
		return false;
	return true;
}
bool isRepeated(int now[], const vector<int>& dira, int a, int step) {
	for (int i = 0; i < step; i++) {
		if (dira[i] == a) {
			return true;
		}
	}
	return false;
}
void display(const vector<int>& dira) {
	for (int i = 0; i <= 17; i++) {
		cout << setw(2) << dira[i];
	}
	cout << endl;
}
void path(const vector<int>& dira) {
	int i = 0;
	while (dira[i] != 0) {
		int prev = (i == 0) ? 0 : dira[i - 1];
		int curr = dira[i];
		int diff = curr - prev;
		
		switch (diff) {
		case 8:
		case -8:
			cout << "农夫独自过河" << endl;
			break;
		case 12:
		case -12:
			cout << "农夫带狼过河" << endl;
			break;
		case 10:
		case -10:
			cout << "农夫带羊过河" << endl;
			break;
		case 9:
		case -9:
			cout << "农夫带菜过河" << endl;
			break;
		default:
			cout << "未知动作" << endl;
			break;
		}
		i++;
	}
}
void backtracking(int now[], vector<int>& dira, int step) {
	int a = now[0] * 8 + now[1] * 4 + now[2] * 2 + now[3] * 1;
	if (isRepeated(now, dira, a, step) || !IsSafe(now)) {
		return;
	}
	dira[step] = a;
	if (now[0] == 0 && now[1] == 0 && now[2] == 0 && now[3] == 0) {
		count++;
		cout << "过河的第" << count << "种方法" << endl;
		path(dira);
		cout << endl;
		return;
	}
	for (int i = 0; i < 4; i++) {
		if (now[i] == now[0]) { // 物体和农夫在同一侧
			int temp[4];
			for (int j = 0; j < 4; j++) {
				temp[j] = now[j]; // 备份当前状态
			}
			
			now[i] = !now[i]; // 移动物体
			if (i != 0) {
				now[0] = !now[0]; // 移动农夫
			}
			backtracking(now, dira, step + 1); // 递归调用
			for (int j = 0; j < 4; j++) {
				now[j] = temp[j]; // 恢复当前状态
			}
		}
	}
}
int main() {
	int now[4] = {1, 1, 1, 1}; // 农夫、狼、鸡、谷子的初始位置都在河的一侧
	vector<int> dira(18, 0);
	backtracking(now, dira, 0); // 调用回溯法函数
	return 0;
}
